home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7889 < prev    next >
Encoding:
Text File  |  1996-08-05  |  5.7 KB  |  176 lines
  1. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  2. Path: sargon.mdl.sandia.gov!news
  3. From: jscuste@sandia.gov (Jon Custer)
  4. Subject: Re: Tough FACTORIAL math problem...
  5. X-Nntp-Posting-Host: custerjs.mdl.sandia.gov
  6. Message-ID: <1996Feb16.182606.20020@mdl.sandia.gov>
  7. Sender: news@mdl.sandia.gov (Usenet News Admin)
  8. Reply-To: jscuste@sandia.gov
  9. Organization: Sandia National Laboratories
  10. X-Newsreader: IBM NewsReader/2 v1.00
  11. References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com> <DMuJwF.734@cwi.nl>
  12. Date: Fri, 16 Feb 1996 18:26:06 GMT
  13.  
  14. In <DMuJwF.734@cwi.nl>, dik@cwi.nl (Dik T. Winter) writes:
  15.  
  16. [deserved flamelet gunched...]
  17.  
  18. >What you and most other posters (except the one I saw in maple, and my
  19. >own of course) forget is that if a number contains factors of 5 you have
  20. >to be aware of all factors 5 plus the remainder divided by all those
  21. >factors. 14! ends in 2, lets see what happens if you multiply by 15.
  22. >First take the factor of 5; this will take 2 to 10 and a last digit
  23. >of 1; but (as you already saw) that is not valid so the last digit will
  24. >become 6.  Now you still have the remaining factor 3 which will take
  25. >6 to 8.  And, indeed, the last non-zero digit of 15! is 8.
  26. >
  27. >Jochen Schoof's solution inherently used a similar table, but he ignored
  28. >the possibility of multiple factors 5.  Which (in his case) did result
  29. >for some factorials in odd last non-zero digits, and that can not happen
  30. >(except for 0! and 1!).
  31. >
  32. >Using only the last k digits of the factorial (excluding trailing zeros)
  33. >and the last l digits of the multiplier will ultimately lead to a
  34. >period.  (The proof is fairly simple.)  But the last non-zero digit of
  35. >the factorial does not show a period; the increasing number of factors 5
  36. >that can occur in a single number prevent this.  So, all such methods
  37. >will fail at some stage.  Taking care of all individual factors 5 solves
  38. >this.
  39. >
  40. >But apparently this is a tough question indeed.  Even an old-timer like
  41. >Jos Horsmeier fell into at least one of the traps.
  42. >-- 
  43. >dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  44. >home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  45.  
  46. OK, let me try my hand at this problem.   It is clear by now that factors of
  47. 5 are a problem.  One way to eliminate them as mentioned above is to eliminate
  48. them and then divide the (previous) factorial by 2 to compensate.  As noted,
  49. this too will eventually fail.
  50.  
  51. Thus, the next iteration, which is to eliminate, but keep track of, all of the
  52. factors of 2 as well.  Then, your "factorial" will always have a non-zero
  53. rightmost digit.  But, you then have to compensate for the powers of 2 (minus
  54. the powers of 10) that you have eliminated up to that point.  Multiplying the 
  55. last digit of you "factorial" by the last digit of the _net_ powers of 2 will
  56. readily yield the last non-zero digit of the factorial.
  57.  
  58. The program is as follows.  It has been compile and run, but I look forward
  59. to having it proved incorrect by others...
  60.  
  61.  
  62. /* Determine last non-zero digit in a factorial */
  63. /* 
  64.    General algorithm:
  65.    1) Eliminate all powers of 2 as they come along.  Keep track of _net_
  66.       number of powers of 2 (see next step).  Last digit of this
  67.       factor is easy to determine in a look up table.
  68.    2) Eliminate all powers of 5 as they come along.  Take away powers of
  69.       2, leaving _net_ powers of 2,  to convert to powers of 10.
  70.       There are always more powers of 2 than powers of 5.  
  71.       All powers of 10 result in no change to last significant digit.
  72.    3) Multiply remainder of factor with previous residual.  Truncate
  73.       to last digit, and reserve for next iteration.  Multiply by
  74.       last digit of _net_ powers of two, take last digit as answer.
  75.    4) Print out result, and loop to next.
  76. */
  77.  
  78. #include <stdlib.h>
  79. #include <stdio.h>
  80.  
  81. /* function prototypes */
  82. unsigned long right_digit(unsigned long i);
  83. unsigned long eliminate_fives(unsigned long *i);
  84. unsigned long eliminate_twos(unsigned long *i);
  85.  
  86. int main(int argc, char * argv[]){
  87.  
  88.     /* keep track of powers of 5s, powers of 2s so far */
  89.     unsigned long p_of_5 = 0ul;
  90.     unsigned long p_of_2 = 0ul;
  91.  
  92.     static unsigned long lookup[4] = {6ul, 2ul, 4ul, 8ul};
  93.  
  94.     unsigned long loop, temp, one, l1, count;
  95.     unsigned long k;
  96.  
  97.     /* get factorial to go to */
  98.     if(argc<2){
  99.         count = 10; /* no number given, print out a few... */
  100.     }
  101.     else{
  102.         count = atol(argv[1]);
  103.     }
  104.  
  105.  
  106.     printf("/* Fact   LD      10's\n");
  107.  
  108.     /* special cases here - 0! and 1! */
  109.      printf("%8ld   %1ld %8ld\n", 0ul, 1ul, 0ul); 
  110.     printf("%8ld   %1ld %8ld\n", 1ul, 1ul, 0ul);
  111.  
  112.     /* Initialize last digit */
  113.     one  = 1ul;
  114.  
  115.     for(loop = 2ul; loop <= count; loop++){
  116.  
  117.         temp = loop;
  118.  
  119.         /* drop all 2's from next factor, keep track of number */
  120.         p_of_2 += eliminate_twos(&temp);
  121.  
  122.         /* drop all 5's from factor */
  123.         k = eliminate_fives(&temp);    
  124.         p_of_5 += k;        /* keep track of total 5's */
  125.         p_of_2 -= k;        /* eliminate 2's to make 10s */
  126.  
  127.         /* multiply remainder and take last digit (always non-zero) */
  128.         one = right_digit(one*temp);
  129.  
  130.         /* now correct for all the powers of two so far */
  131.         l1  = right_digit(one*lookup[(p_of_2 % 4)]);
  132.  
  133.         printf("%8ld   %ld %8ld\n", loop, l1, p_of_5);
  134.  
  135.     }
  136.  
  137.     return(0);
  138.  
  139. }
  140.  
  141. unsigned long right_digit(unsigned long i){
  142.     return (i % 10ul);
  143. }
  144.  
  145. /* returns number of powers of 5 found in this integer, alters integer */
  146. unsigned long eliminate_fives(unsigned long *i){
  147.     unsigned long q;
  148.  
  149.     q = 0ul;
  150.     while(!(*i % 5ul)){
  151.         *i = *i/5ul;
  152.         q++;
  153.     }
  154.     return(q);
  155. }
  156.  
  157. /* returns number of powers of 2 found in this integer, alters integer */
  158. unsigned long eliminate_twos(unsigned long *i){
  159.     unsigned long q;
  160.  
  161.     q = 0ul;
  162.     while(!(*i % 2ul)){
  163.         *i = *i/2ul;
  164.         q++;
  165.     }
  166.     return(q);
  167. }
  168.  
  169. Cheers, Jon Custer
  170.  
  171. (Dik -- greetings to all folks on the Kruislaan.  I spent 3 years across
  172. the way from you at FOM-AMOLF.)
  173.  
  174.  
  175.  
  176.